package sorting;

import java.util.Arrays;

import util.ArrayUtil;

public class CountingSortInPlace {
	public static void sort(short[] numbers, short size)
	{
		Interval[] intervals = new Interval[size];
		
		for(int i = 0; i < size; i ++)
		{
			intervals[i] = new Interval(0, -1);
		}
		
		for(int i = 0, length = numbers.length; i < length; i ++ )
		{
			Interval interval = intervals[numbers[i]];
			interval.setEnd(interval.getEnd() + 1);
		}
		
		for(int i = 1, length = intervals.length; i < length; i ++)
		{
			Interval interval = intervals[i];
			interval.setBegin(intervals[i - 1].getEnd() + 1);
			interval.setEnd(interval.getBegin() + interval.getEnd());
		}
		
		int i = 0, length = numbers.length;
		while(i < length)
		{
			Interval interval = intervals[numbers[i]];
			if(interval.getEnd() >= interval.getBegin() && (i > interval.getEnd() || i < interval.getBegin()))
			{
				ArrayUtil.each(numbers, i, (int)interval.getBegin());
				interval.setBegin(interval.getBegin() + 1);
			}
			else
			{
				i ++;
			}
		}
	}
	
	public static void main(String[] args) {
		short[] numbers = {1, 1, 3, 1, 3, 4, 2, 5, 3, 2, 0, 2, 0, 5};
		sort(numbers, (short)6);
		System.out.println(Arrays.toString(numbers));
	}
}